import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
//    public TreeNode createTree1(){
//        TreeNode A = new TreeNode('A');
//        TreeNode B = new TreeNode('B');
//        TreeNode C = new TreeNode('C');
//        TreeNode D = new TreeNode('D');
//        TreeNode E = new TreeNode('E');
//        TreeNode F = new TreeNode('F');
//        TreeNode G = new TreeNode('G');
//        TreeNode H = new TreeNode('H');
//        A.left = B;
//        A.right = C;
//        B.left = D;
//        B.right = E;
//        E.right = H;
//        C.left = F;
//        C.right = G;
//        return A;
//    }
    public TreeNode createTree1(){
        TreeNode node1 = new TreeNode(10);
        TreeNode node2 = new TreeNode(6);
        TreeNode node4 = new TreeNode(14);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(8);
        TreeNode node7 = new TreeNode(12);
        TreeNode node8 = new TreeNode(16);
        node1.left = node2;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;
        return node1;
    }
    public TreeNode createTree2(){
        TreeNode node1 = new TreeNode(1);
        return node1;
    }
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }
    public int getLeafsizecount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafsizecount(root.left) + getLeafsizecount(root.right);
    }
    public int getKLevelNodeCount(TreeNode root, int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return  leftH > rightH ? leftH + 1 : rightH + 1;
    }
    public TreeNode find(TreeNode root, char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode leftRet = find(root.left, val);
        if(leftRet != null){    //左子树不为空，那么就一定在左子树找到了，不用去右子树去找了，直接返回
            return leftRet;
        }
        TreeNode rightRet = find(root.right, val);
        if(rightRet != null){
            return rightRet;
        }
        return null;    //左右子树都为空，说明都没找到，直接返回null
    }
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); //先把根节点入队列
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){ //左右子树的节点不为空就入队列
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break; //遇到空节点就break
            }
        }
        while(!queue.isEmpty()){    //空节点后还有非空节点就不是完全二叉树
            TreeNode cur = queue.poll();
            if(cur != null){
                return false;
            }
        }
        return true;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(root.val == subRoot.val){
            return isSameTree(root, subRoot);
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null && q != null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        if (p.val != q.val) { //走到这里，p和q都不为空
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode prev = null;   //标记已经打印过的节点
        while (cur != null || !st.empty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            top = st.peek(); //这里不能pop, 要把右子树遍历完才能出栈
            cur = top.right;
            if(cur == null || prev == cur){    //排除打印过的节点入栈
                st.pop();
                ret.add(top.val);
                prev = top;
                cur = st.peek();

            }
        }
        return ret;
    }

    public static TreeNode cur = null;
    public static TreeNode retList = cur;
    public void ListInorder(TreeNode root){
        if(root == null){
            return;
        }
        ListInorder(root.left);
        cur = root;
        cur = cur.right;
        ListInorder(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        ListInorder(pRootOfTree);
       return retList;
    }
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree1();
       TreeNode ret = binaryTree.Convert(root);
        System.out.println("hehe");
    }

}